package 数组题目.前缀和与差分;

import java.util.ArrayList;

//最后 K 个数的乘积
//https://leetcode.cn/problems/product-of-the-last-k-numbers/description/
class 最后K个数的乘积 {
    // 前缀积数组
    // preProduct[i] / preProduct[j] 就是 [i, j] 之间的元素积
    ArrayList<Integer> preProduct = new ArrayList<>();

    public 最后K个数的乘积() {
        // 初始化放一个 1，便于计算后续添加元素的乘积
        preProduct.add(1);
    }

    public void add(int num) {
        if (num == 0) {
            // 如果添加的元素是 0，则前面的元素积都废了
            preProduct.clear();
            preProduct.add(1);
            return;
        }
        int n = preProduct.size();
        // 前缀积数组中每个元素
        preProduct.add(preProduct.get(n - 1) * num);
    }

    public int getProduct(int k) {
        int n = preProduct.size();
        if (k > n - 1) {
            // 不足 k 个元素，是因为最后 k 个元素存在 0
            return 0;
        }
        // 计算最后 k 个元素积
        return preProduct.get(n - 1) / preProduct.get(n - k - 1);
    }

    public static void main(String[] args) {
        最后K个数的乘积 p = new 最后K个数的乘积();
        p.add(1);
        p.add(3);
        p.add(0);
        p.add(2);
        p.add(5);
        p.add(4);
        System.out.println(p.getProduct(2));
    }
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers obj = new ProductOfNumbers();
 * obj.add(num);
 * int param_2 = obj.getProduct(k);
 */
